package leetCode.offer14_i;

public class Solution2 implements Solution{


    /**
     * 解法：对这个题目，我们可以先采用举例法看看有什么规律
     * 定义f(n) 就是n的最大乘积
     * f(1) = 0
     * f(2) = 1
     * f(3) = 1*2 = 2
     * f(4) = 2*2 = 4
     * f(5) = 2*3 = 6
     * f(6) = 3*3 = 9
     * f(7) = 2*2*3 = 12
     * 到这里，我们能否看到，4之后的所有最大乘积的元素组成不是2就是3。
     * 我们是不是可以顺着这个思路来，将元素拆成只有2，3组成的数组，然后相乘就能得到我们要的结果了
     * @param n
     * @return
     */
    @Override
    public int cuttingRope(int n) {
        if(n<2) return 0;
        if(n==2) return 1;
        if(n==3) return 2;

        if(n%3==0) return (int) Math.pow(3,n/3);
        else{
            for(int i=n-2;i>=2;i-=2){
                if(i%3==0) {
                    return (int) Math.pow(3,i/3)*(int)Math.pow(2,(n-i)/2);
                }
            }
        }
        return (int)Math.pow(2,n/2);
    }

    public static void main(String[] args) {
        Solution2 solution1 = new Solution2();
        System.out.println(solution1.cuttingRope(5));
    }
}
